<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>HashMap底层实现和原理 | flybird&#39;s blog</title>
    <meta name="generator" content="VuePress 1.8.0">
    <link rel="icon" href="https://infinitypro-img.infinitynewtab.com/custom-icon/8001de1jd3n68lbfnxxt564xvb0vl5.png?imageMogr2/thumbnail/240x/format/webp/blur/1x0/quality/100|imageslim">
    <script language="javascript" type="text/javascript" src="https://cdn.staticfile.org/jquery/1.7.2/jquery.min.js"></script>
    <script language="javascript" type="text/javascript" src="/js/MouseClickEffect.js"></script>
    <meta name="description" content="Stay hungry, Stay foolish">
    <meta name="viewport" content="width=device-width,initial-scale=1,user-scalable=no">
    
    <link rel="preload" href="/assets/css/0.styles.324c77a5.css" as="style"><link rel="preload" href="/assets/js/app.55c4f7c3.js" as="script"><link rel="preload" href="/assets/js/5.86109dd2.js" as="script"><link rel="preload" href="/assets/js/1.74974061.js" as="script"><link rel="preload" href="/assets/js/2.ab8aa845.js" as="script"><link rel="preload" href="/assets/js/63.84bfbbbf.js" as="script"><link rel="preload" href="/assets/js/18.cfe435f1.js" as="script"><link rel="prefetch" href="/assets/js/10.1f3187f9.js"><link rel="prefetch" href="/assets/js/11.67fe3d1f.js"><link rel="prefetch" href="/assets/js/12.0052f325.js"><link rel="prefetch" href="/assets/js/13.bad60b36.js"><link rel="prefetch" href="/assets/js/14.6a893378.js"><link rel="prefetch" href="/assets/js/15.899648d3.js"><link rel="prefetch" href="/assets/js/16.0575f88b.js"><link rel="prefetch" href="/assets/js/17.86f820d7.js"><link rel="prefetch" href="/assets/js/19.1d1c7b67.js"><link rel="prefetch" href="/assets/js/20.218819f6.js"><link rel="prefetch" href="/assets/js/21.223949af.js"><link rel="prefetch" href="/assets/js/22.eb6ea80c.js"><link rel="prefetch" href="/assets/js/23.cf07ba0c.js"><link rel="prefetch" href="/assets/js/24.eeb9d511.js"><link rel="prefetch" href="/assets/js/25.4be64ae7.js"><link rel="prefetch" href="/assets/js/26.6aea0ced.js"><link rel="prefetch" href="/assets/js/27.7540f161.js"><link rel="prefetch" href="/assets/js/28.d88a26e6.js"><link rel="prefetch" href="/assets/js/29.7edc404c.js"><link rel="prefetch" href="/assets/js/30.b3c16bef.js"><link rel="prefetch" href="/assets/js/31.63392d40.js"><link rel="prefetch" href="/assets/js/32.b90695c8.js"><link rel="prefetch" href="/assets/js/33.669186a5.js"><link rel="prefetch" href="/assets/js/34.57a9b7fc.js"><link rel="prefetch" href="/assets/js/35.81d5b8b3.js"><link rel="prefetch" href="/assets/js/36.466fde53.js"><link rel="prefetch" href="/assets/js/37.ff7b9321.js"><link rel="prefetch" href="/assets/js/38.132de18a.js"><link rel="prefetch" href="/assets/js/39.80a51963.js"><link rel="prefetch" href="/assets/js/40.e7d6c67d.js"><link rel="prefetch" href="/assets/js/41.d195ea4b.js"><link rel="prefetch" href="/assets/js/42.dbe1a8f1.js"><link rel="prefetch" href="/assets/js/43.2ea02aec.js"><link rel="prefetch" href="/assets/js/44.294015bc.js"><link rel="prefetch" href="/assets/js/45.3cf9c326.js"><link rel="prefetch" href="/assets/js/46.8cc95701.js"><link rel="prefetch" href="/assets/js/47.ddf6cc44.js"><link rel="prefetch" href="/assets/js/48.ba718ca6.js"><link rel="prefetch" href="/assets/js/49.feee5279.js"><link rel="prefetch" href="/assets/js/50.6f2d0d0d.js"><link rel="prefetch" href="/assets/js/51.ebe1eb07.js"><link rel="prefetch" href="/assets/js/52.3e47f7ae.js"><link rel="prefetch" href="/assets/js/53.861fb703.js"><link rel="prefetch" href="/assets/js/54.f7d3a937.js"><link rel="prefetch" href="/assets/js/55.d90baa98.js"><link rel="prefetch" href="/assets/js/56.ba7f3256.js"><link rel="prefetch" href="/assets/js/57.90441d7f.js"><link rel="prefetch" href="/assets/js/58.a0d58abc.js"><link rel="prefetch" href="/assets/js/59.7f649313.js"><link rel="prefetch" href="/assets/js/6.00dfc51e.js"><link rel="prefetch" href="/assets/js/60.60dd83d2.js"><link rel="prefetch" href="/assets/js/61.b84cd1ef.js"><link rel="prefetch" href="/assets/js/62.8ed6541f.js"><link rel="prefetch" href="/assets/js/64.01c483db.js"><link rel="prefetch" href="/assets/js/65.278ce63e.js"><link rel="prefetch" href="/assets/js/66.cb493053.js"><link rel="prefetch" href="/assets/js/67.8c2201b6.js"><link rel="prefetch" href="/assets/js/68.46467c87.js"><link rel="prefetch" href="/assets/js/69.ee34297d.js"><link rel="prefetch" href="/assets/js/7.aaee1baa.js"><link rel="prefetch" href="/assets/js/70.3a016bcf.js"><link rel="prefetch" href="/assets/js/71.1cb787d0.js"><link rel="prefetch" href="/assets/js/72.2ee0677e.js"><link rel="prefetch" href="/assets/js/73.3e1e1729.js"><link rel="prefetch" href="/assets/js/74.947d7cd3.js"><link rel="prefetch" href="/assets/js/75.2e5c7344.js"><link rel="prefetch" href="/assets/js/76.6c098cc2.js"><link rel="prefetch" href="/assets/js/77.03fd3a89.js"><link rel="prefetch" href="/assets/js/78.38d2d963.js"><link rel="prefetch" href="/assets/js/79.ea508df9.js"><link rel="prefetch" href="/assets/js/8.35d0b089.js"><link rel="prefetch" href="/assets/js/80.b2b1dda3.js"><link rel="prefetch" href="/assets/js/81.d7db5a4d.js"><link rel="prefetch" href="/assets/js/82.1c148069.js"><link rel="prefetch" href="/assets/js/83.51e2c0d0.js"><link rel="prefetch" href="/assets/js/84.6118b266.js"><link rel="prefetch" href="/assets/js/85.55a516f8.js"><link rel="prefetch" href="/assets/js/86.3b73f7a9.js"><link rel="prefetch" href="/assets/js/87.123149cb.js"><link rel="prefetch" href="/assets/js/88.f87dde9d.js"><link rel="prefetch" href="/assets/js/89.06c3b9a1.js"><link rel="prefetch" href="/assets/js/9.58e6c220.js"><link rel="prefetch" href="/assets/js/vendors~flowchart.080f3458.js">
    <link rel="stylesheet" href="/assets/css/0.styles.324c77a5.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div><div class="theme-container" data-v-0b87bb44><div data-v-0b87bb44><div id="loader-wrapper" class="loading-wrapper" data-v-1c4f0192 data-v-0b87bb44 data-v-0b87bb44><div class="loader-main" data-v-1c4f0192><div data-v-1c4f0192></div><div data-v-1c4f0192></div><div data-v-1c4f0192></div><div data-v-1c4f0192></div></div> <!----> <!----></div> <div class="password-shadow password-wrapper-out" style="display:none;" data-v-73c95a87 data-v-0b87bb44 data-v-0b87bb44><h3 class="title" style="display:none;" data-v-73c95a87 data-v-73c95a87>flybird's blog</h3> <!----> <label id="box" class="inputBox" style="display:none;" data-v-73c95a87 data-v-73c95a87><input type="password" value="" data-v-73c95a87> <span data-v-73c95a87>Konck! Knock!</span> <button data-v-73c95a87>OK</button></label> <div class="footer" style="display:none;" data-v-73c95a87 data-v-73c95a87><span data-v-73c95a87><i class="iconfont reco-theme" data-v-73c95a87></i> <a target="blank" href="https://vuepress-theme-reco.recoluan.com" data-v-73c95a87>vuePress-theme-reco</a></span> <span data-v-73c95a87><i class="iconfont reco-copyright" data-v-73c95a87></i> <a data-v-73c95a87><span data-v-73c95a87>flybird</span>
            
          <span data-v-73c95a87>2020 - </span>
          2021
        </a></span></div></div> <div class="hide" data-v-0b87bb44><header class="navbar" data-v-0b87bb44><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">flybird's blog</span></a> <div class="links"><div class="color-picker"><a class="color-button"><i class="iconfont reco-color"></i></a> <div class="color-picker-menu" style="display:none;"><div class="mode-options"><h4 class="title">Choose mode</h4> <ul class="color-mode-options"><li class="dark">dark</li><li class="auto active">auto</li><li class="light">light</li></ul></div></div></div> <div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/index.html" class="nav-link"><i class="iconfont reco-home"></i>
  主页
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="iconfont reco-category"></i>
      分类
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/categories/大数据/" class="nav-link"><i class="iconfont undefined"></i>
  大数据
</a></li><li class="dropdown-item"><!----> <a href="/categories/后端/" class="nav-link"><i class="iconfont undefined"></i>
  后端
</a></li><li class="dropdown-item"><!----> <a href="/categories/中间件/" class="nav-link"><i class="iconfont undefined"></i>
  中间件
</a></li></ul></div></div><div class="nav-item"><a href="/tag/" class="nav-link"><i class="iconfont reco-tag"></i>
  标签
</a></div><div class="nav-item"><a href="/timeline/" class="nav-link"><i class="iconfont reco-date"></i>
  时间线
</a></div><div class="nav-item"><a href="/about/" class="nav-link"><i class="iconfont reco-message"></i>
  关于我
</a></div> <a href="https://github.com/f1ybird" target="_blank" rel="noopener noreferrer" class="repo-link"><i class="iconfont reco-github"></i>
    GitHub
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask" data-v-0b87bb44></div> <aside class="sidebar" data-v-0b87bb44><div class="personal-info-wrapper" data-v-7e653f02><img src="/vuepress/my-head.png" alt="author-avatar" class="personal-img" data-v-7e653f02> <h3 class="name" data-v-7e653f02>
    flybird
  </h3> <div class="num" data-v-7e653f02><div data-v-7e653f02><h3 data-v-7e653f02>63</h3> <h6 data-v-7e653f02>文章</h6></div> <div data-v-7e653f02><h3 data-v-7e653f02>26</h3> <h6 data-v-7e653f02>标签</h6></div></div> <hr data-v-7e653f02></div> <nav class="nav-links"><div class="nav-item"><a href="/index.html" class="nav-link"><i class="iconfont reco-home"></i>
  主页
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="iconfont reco-category"></i>
      分类
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/categories/大数据/" class="nav-link"><i class="iconfont undefined"></i>
  大数据
</a></li><li class="dropdown-item"><!----> <a href="/categories/后端/" class="nav-link"><i class="iconfont undefined"></i>
  后端
</a></li><li class="dropdown-item"><!----> <a href="/categories/中间件/" class="nav-link"><i class="iconfont undefined"></i>
  中间件
</a></li></ul></div></div><div class="nav-item"><a href="/tag/" class="nav-link"><i class="iconfont reco-tag"></i>
  标签
</a></div><div class="nav-item"><a href="/timeline/" class="nav-link"><i class="iconfont reco-date"></i>
  时间线
</a></div><div class="nav-item"><a href="/about/" class="nav-link"><i class="iconfont reco-message"></i>
  关于我
</a></div> <a href="https://github.com/f1ybird" target="_blank" rel="noopener noreferrer" class="repo-link"><i class="iconfont reco-github"></i>
    GitHub
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav>  <ul class="sidebar-links"><li><a href="/views/" aria-current="page" class="sidebar-link">概览</a></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>大数据</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>中间件</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>后端</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/views/java/ArrayList.html" class="sidebar-link">ArrayList底层实现和原理</a></li><li><a href="/views/java/HashMap.html" aria-current="page" class="active sidebar-link">HashMap底层实现和原理</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/views/java/HashMap.html#简介" class="sidebar-link">简介</a></li><li class="sidebar-sub-header"><a href="/views/java/HashMap.html#继承关系" class="sidebar-link">继承关系</a></li><li class="sidebar-sub-header"><a href="/views/java/HashMap.html#实现原理" class="sidebar-link">实现原理</a></li><li class="sidebar-sub-header"><a href="/views/java/HashMap.html#手写一个简单的hashmap" class="sidebar-link">手写一个简单的HashMap</a></li><li class="sidebar-sub-header"><a href="/views/java/HashMap.html#hashmap的扩容机制-resize" class="sidebar-link">HashMap的扩容机制 resize()</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/views/java/HashMap.html#hashmap的负载因子" class="sidebar-link">HashMap的负载因子</a></li><li class="sidebar-sub-header"><a href="/views/java/HashMap.html#先说hashmap底层数组长度扩容为什么是2的幂次方数-其实就是为了使hash均匀分组" class="sidebar-link">先说HashMap底层数组长度扩容为什么是2的幂次方数(其实就是为了使hash均匀分组)</a></li><li class="sidebar-sub-header"><a href="/views/java/HashMap.html#再来说hashmap的resize" class="sidebar-link">再来说HashMap的resize()</a></li></ul></li><li class="sidebar-sub-header"><a href="/views/java/HashMap.html#hashmap面试题" class="sidebar-link">HashMap面试题</a></li></ul></li><li><a href="/views/java/docker.html" class="sidebar-link">Docker的基本了解和使用</a></li><li><a href="/views/java/itext.html" class="sidebar-link">itext:PDF导出</a></li><li><a href="/views/java/poi.html" class="sidebar-link">poi多线程多sheet导出Excel,csv</a></li><li><a href="/views/java/quartz.html" class="sidebar-link">Quartz定时任务</a></li><li><a href="/views/java/rabbitmq001.html" class="sidebar-link">RabbitMQ基础</a></li><li><a href="/views/java/rabbitmq002.html" class="sidebar-link">RabbitMQ进阶</a></li><li><a href="/views/java/redis01.html" class="sidebar-link">Redis基础</a></li><li><a href="/views/java/redis02.html" class="sidebar-link">Redis终结</a></li><li><a href="/views/java/SSH.html" class="sidebar-link">SSH架构知识点概览</a></li><li><a href="/views/java/jwt.html" class="sidebar-link">JWT登陆认证</a></li><li><a href="/views/java/swagger2.html" class="sidebar-link">Swagger2的基本了解和使用</a></li><li><a href="/views/java/thread.html" class="sidebar-link">多线程和线程池基础</a></li><li><a href="/views/java/ThreadPool.html" class="sidebar-link">线程池进阶详解</a></li><li><a href="/views/java/ThreadLocal.html" class="sidebar-link">ThreadLocal简介</a></li><li><a href="/views/java/annotationLog.html" class="sidebar-link">注解+AOP实现日志记录</a></li><li><a href="/views/java/jvm.html" class="sidebar-link">jvm和GC</a></li><li><a href="/views/java/JUC.html" class="sidebar-link">JUC小结</a></li><li><a href="/views/java/javaLock.html" class="sidebar-link">Java中的各种锁</a></li><li><a href="/views/java/mysql_explain.html" class="sidebar-link">MySQL慢查询优化</a></li><li><a href="/views/java/ReentrantLock.html" class="sidebar-link">ReentrantLock 详解</a></li></ul></section></li></ul> </aside> <div class="password-shadow password-wrapper-in" style="display:none;" data-v-73c95a87 data-v-0b87bb44><h3 class="title" style="display:none;" data-v-73c95a87 data-v-73c95a87>HashMap底层实现和原理</h3> <!----> <label id="box" class="inputBox" style="display:none;" data-v-73c95a87 data-v-73c95a87><input type="password" value="" data-v-73c95a87> <span data-v-73c95a87>Konck! Knock!</span> <button data-v-73c95a87>OK</button></label> <div class="footer" style="display:none;" data-v-73c95a87 data-v-73c95a87><span data-v-73c95a87><i class="iconfont reco-theme" data-v-73c95a87></i> <a target="blank" href="https://vuepress-theme-reco.recoluan.com" data-v-73c95a87>vuePress-theme-reco</a></span> <span data-v-73c95a87><i class="iconfont reco-copyright" data-v-73c95a87></i> <a data-v-73c95a87><span data-v-73c95a87>flybird</span>
            
          <span data-v-73c95a87>2020 - </span>
          2021
        </a></span></div></div> <div data-v-0b87bb44><main class="page"><!----> <div class="page-title" style="display:none;"><h1>HashMap底层实现和原理</h1> <hr> <div data-v-7b2e794a><i class="iconfont reco-account" data-v-7b2e794a><span data-v-7b2e794a>flybird</span></i> <i class="iconfont reco-date" data-v-7b2e794a><span data-v-7b2e794a>2019-06-13 20:53:26</span></i> <i class="iconfont reco-eye" data-v-7b2e794a><span id="/views/java/HashMap.html" data-flag-title="Your Article Title" class="leancloud-visitors" data-v-7b2e794a><a class="leancloud-visitors-count" style="font-size:.9rem;font-weight:normal;color:#999;"></a></span></i> <i class="iconfont reco-tag tags" data-v-7b2e794a><span class="tag-item" data-v-7b2e794a>
      源码分析
    </span><span class="tag-item" data-v-7b2e794a>
      Java
    </span></i></div></div> <div class="theme-reco-content content__default" style="display:none;"><div id="boxx" data-v-f4ca0dac><div data-v-f4ca0dac><p v-if="true" class="custom-block-title" data-v-f4ca0dac></p> <p v-if="true" data-v-f4ca0dac></p></div></div> <p></p><div class="table-of-contents"><ul><li><a href="#简介">简介</a></li><li><a href="#继承关系">继承关系</a></li><li><a href="#实现原理">实现原理</a></li><li><a href="#手写一个简单的hashmap">手写一个简单的HashMap</a></li><li><a href="#hashmap的扩容机制-resize">HashMap的扩容机制 resize()</a><ul><li><a href="#hashmap的负载因子">HashMap的负载因子</a></li><li><a href="#先说hashmap底层数组长度扩容为什么是2的幂次方数-其实就是为了使hash均匀分组">先说HashMap底层数组长度扩容为什么是2的幂次方数(其实就是为了使hash均匀分组)</a></li><li><a href="#再来说hashmap的resize">再来说HashMap的resize()</a></li></ul></li><li><a href="#hashmap面试题">HashMap面试题</a></li></ul></div><p></p> <h1 id="hashmap底层实现和原理"><a href="#hashmap底层实现和原理" class="header-anchor">#</a> HashMap底层实现和原理</h1> <h2 id="简介"><a href="#简介" class="header-anchor">#</a> 简介</h2> <ul><li>HashMap是一个散列桶（数组和链表），它存储的内容是键值对(key-value)映射</li> <li>HashMap采用了数组和链表的数据结构，方便继承了数组的线性查找和链表的寻址修改</li> <li>HashMap是非synchronized（但是在rehash和扩容的时候可能出现并发问题），所以HashMap很快</li> <li>HashMap可以接受null键和值，而Hashtable则不能（原因就是equlas()方法需要对象）</li></ul> <h2 id="继承关系"><a href="#继承关系" class="header-anchor">#</a> 继承关系</h2> <div class="language-java line-numbers-mode"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">HashMap</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> <span class="token keyword">extends</span> <span class="token class-name">AbstractMap</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span>
    <span class="token keyword">implements</span> <span class="token class-name">Map</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">,</span> <span class="token class-name">Cloneable</span><span class="token punctuation">,</span> <span class="token class-name">Serializable</span> <span class="token punctuation">{</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><h2 id="实现原理"><a href="#实现原理" class="header-anchor">#</a> 实现原理</h2> <ul><li>HashMap由数组+链表(+红黑树 1.8)来实现对数据的存储</li> <li>详细可以看：<a href="https://blog.csdn.net/visant/article/details/80045154" target="_blank" rel="noopener noreferrer">HashMap原理深入理解<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ul> <p><img src="/znote/img/HashMap/20180423002750407.png" alt=""></p> <h2 id="手写一个简单的hashmap"><a href="#手写一个简单的hashmap" class="header-anchor">#</a> 手写一个简单的HashMap</h2> <ul><li>很简单，就是看一下HashMap源码中定义了什么属性、方法，然后我们写一个简单的类继承HashMap，挑其中几个重要的方法做出实现就好了</li></ul> <div class="language-java line-numbers-mode"><pre class="language-java"><code><span class="token keyword">package</span> <span class="token namespace">com<span class="token punctuation">.</span>eee</span><span class="token punctuation">;</span>

<span class="token keyword">import</span> <span class="token namespace">java<span class="token punctuation">.</span>util<span class="token punctuation">.</span></span><span class="token class-name">HashMap</span><span class="token punctuation">;</span>

<span class="token comment">/**
 * @className: MyHashMap
 * @descripe: 模拟HashMap底层实现
 * @author: zpj
 * @date: 2019/6/7
 * @version: 1.0
 */</span>
<span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">MyHashMap</span><span class="token generics"><span class="token punctuation">&lt;</span>key<span class="token punctuation">,</span>value<span class="token punctuation">&gt;</span></span> <span class="token keyword">extends</span> <span class="token class-name">HashMap</span><span class="token generics"><span class="token punctuation">&lt;</span>key<span class="token punctuation">,</span>value<span class="token punctuation">&gt;</span></span><span class="token punctuation">{</span>

    <span class="token comment">//定义一个数组</span>
    <span class="token keyword">private</span> <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span>key<span class="token punctuation">,</span>value<span class="token punctuation">&gt;</span></span><span class="token punctuation">[</span><span class="token punctuation">]</span> table<span class="token punctuation">;</span> 
    <span class="token comment">//初始化数组容量大小为 16</span>
    <span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token class-name">Integer</span> CSHSZRL <span class="token operator">=</span> <span class="token number">16</span><span class="token punctuation">;</span>
    <span class="token comment">//定义一个size，用来统计HashMap内个数</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> size <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">MyHashMap</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">//创建对象的时候就初始化数组</span>
        table <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">[</span>CSHSZRL<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> size<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> value <span class="token function">get</span><span class="token punctuation">(</span><span class="token class-name">Object</span> key<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">//算出这个节点是在哪个hash组</span>
        <span class="token keyword">int</span> hash <span class="token operator">=</span> key<span class="token punctuation">.</span><span class="token function">hashCode</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> index <span class="token operator">=</span> hash <span class="token operator">%</span> table<span class="token punctuation">.</span>length<span class="token punctuation">;</span>

        <span class="token comment">//遍历</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span>key<span class="token punctuation">,</span>value<span class="token punctuation">&gt;</span></span> node <span class="token operator">=</span> table<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">;</span>table<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token operator">!=</span><span class="token keyword">null</span><span class="token punctuation">;</span>node<span class="token punctuation">.</span><span class="token function">getNext</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token comment">//新元素和老元素一样的话</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span><span class="token function">getK</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token keyword">return</span> node<span class="token punctuation">.</span><span class="token function">getV</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">containsKey</span><span class="token punctuation">(</span><span class="token class-name">Object</span> key<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">super</span><span class="token punctuation">.</span><span class="token function">containsKey</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">/**
     * HashMap的 put()方法
     * @param key
     * @param value
     * @return 当put元素出现重复的时候，新元素覆盖老元素，返回老元素的value
     */</span>
    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> value <span class="token function">put</span><span class="token punctuation">(</span>key key<span class="token punctuation">,</span> value value<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">//算出这个节点是在哪个hash组</span>
        <span class="token keyword">int</span> hash <span class="token operator">=</span> key<span class="token punctuation">.</span><span class="token function">hashCode</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> index <span class="token operator">=</span> hash <span class="token operator">%</span> table<span class="token punctuation">.</span>length<span class="token punctuation">;</span>

        <span class="token comment">//新增元素时，遍历老元素，和新元素比较</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span>key<span class="token punctuation">,</span>value<span class="token punctuation">&gt;</span></span> node <span class="token operator">=</span> table<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">;</span>table<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token operator">!=</span><span class="token keyword">null</span><span class="token punctuation">;</span>node<span class="token punctuation">.</span><span class="token function">getNext</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token comment">//新元素和老元素一样的话</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>k<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                value oldValue <span class="token operator">=</span> node<span class="token punctuation">.</span>v<span class="token punctuation">;</span>
                node<span class="token punctuation">.</span>v<span class="token operator">=</span>value<span class="token punctuation">;</span>
                <span class="token keyword">return</span> oldValue<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        
        <span class="token comment">//当put第N个元素</span>
        <span class="token function">addNode</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span> value<span class="token punctuation">,</span> index<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">private</span> <span class="token keyword">void</span> <span class="token function">addNode</span><span class="token punctuation">(</span>key key<span class="token punctuation">,</span> value value<span class="token punctuation">,</span> <span class="token keyword">int</span> index<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">//Node&lt;key, value&gt; node = new Node&lt;&gt;(key, value, null);//这个hash组是空的，put第一个元素</span>
        <span class="token comment">//table[index] = node;</span>

        <span class="token comment">//老节点对象</span>
        <span class="token class-name">Node</span> node <span class="token operator">=</span> table<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token comment">//再把新的节点对象追加到原先节点头部,形成链表</span>
        table<span class="token punctuation">[</span>index<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span>value<span class="token punctuation">,</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">//每增加一个元素，HashMap内 个数加1</span>
        size<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> value <span class="token function">remove</span><span class="token punctuation">(</span><span class="token class-name">Object</span> key<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">super</span><span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">/**
     * 源码中定义了一个节点类对象，用来存放每个数据
     * @param &lt;K&gt;
     * @param &lt;V&gt;
     */</span>
    <span class="token keyword">static</span> <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> <span class="token punctuation">{</span>

        <span class="token keyword">private</span> <span class="token class-name">K</span> k<span class="token punctuation">;</span>
        <span class="token keyword">private</span> <span class="token class-name">V</span> v<span class="token punctuation">;</span>
        <span class="token comment">//用来充当链表</span>
        <span class="token keyword">private</span> <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> next<span class="token punctuation">;</span>

        <span class="token comment">//可以传入新元素，然后构成链表</span>
        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">K</span> k<span class="token punctuation">,</span> <span class="token class-name">V</span> v<span class="token punctuation">,</span> <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span> <span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> next<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>k <span class="token operator">=</span> k<span class="token punctuation">;</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>v <span class="token operator">=</span> v<span class="token punctuation">;</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token class-name">K</span> <span class="token function">getK</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> k<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token class-name">V</span> <span class="token function">getV</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> v<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span> <span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> <span class="token function">getNext</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token class-name">MyHashMap</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">String</span><span class="token punctuation">,</span><span class="token class-name">String</span><span class="token punctuation">&gt;</span></span> myHashMap <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyHashMap</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>x<span class="token operator">&lt;</span><span class="token number">10</span><span class="token punctuation">;</span>x<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            myHashMap<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span>x<span class="token operator">+</span><span class="token string">&quot;貂蝉&quot;</span><span class="token punctuation">,</span>x<span class="token operator">+</span><span class="token string">&quot;貂蝉配吕布&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        myHashMap<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token string">&quot;8貂蝉&quot;</span><span class="token punctuation">,</span><span class="token string">&quot;8貂蝉戏吕布&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>myHashMap<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token string">&quot;8貂蝉&quot;</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>myHashMap<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br><span class="line-number">84</span><br><span class="line-number">85</span><br><span class="line-number">86</span><br><span class="line-number">87</span><br><span class="line-number">88</span><br><span class="line-number">89</span><br><span class="line-number">90</span><br><span class="line-number">91</span><br><span class="line-number">92</span><br><span class="line-number">93</span><br><span class="line-number">94</span><br><span class="line-number">95</span><br><span class="line-number">96</span><br><span class="line-number">97</span><br><span class="line-number">98</span><br><span class="line-number">99</span><br><span class="line-number">100</span><br><span class="line-number">101</span><br><span class="line-number">102</span><br><span class="line-number">103</span><br><span class="line-number">104</span><br><span class="line-number">105</span><br><span class="line-number">106</span><br><span class="line-number">107</span><br><span class="line-number">108</span><br><span class="line-number">109</span><br><span class="line-number">110</span><br><span class="line-number">111</span><br><span class="line-number">112</span><br><span class="line-number">113</span><br><span class="line-number">114</span><br><span class="line-number">115</span><br><span class="line-number">116</span><br><span class="line-number">117</span><br><span class="line-number">118</span><br><span class="line-number">119</span><br><span class="line-number">120</span><br><span class="line-number">121</span><br><span class="line-number">122</span><br><span class="line-number">123</span><br><span class="line-number">124</span><br><span class="line-number">125</span><br><span class="line-number">126</span><br><span class="line-number">127</span><br><span class="line-number">128</span><br><span class="line-number">129</span><br><span class="line-number">130</span><br><span class="line-number">131</span><br><span class="line-number">132</span><br><span class="line-number">133</span><br><span class="line-number">134</span><br><span class="line-number">135</span><br><span class="line-number">136</span><br><span class="line-number">137</span><br><span class="line-number">138</span><br><span class="line-number">139</span><br></div></div><h2 id="hashmap的扩容机制-resize"><a href="#hashmap的扩容机制-resize" class="header-anchor">#</a> HashMap的扩容机制 resize()</h2> <ul><li>这一节是整个文章的重点，也是我学习的重点笔记，从这我也理解了为什么阿里规范手册中初始化HashMap的时候要指定大小。</li></ul> <h3 id="hashmap的负载因子"><a href="#hashmap的负载因子" class="header-anchor">#</a> HashMap的负载因子</h3> <ol><li>负载因子loadFactor保持在0.75f是在时间跟空间上达到一个平衡，实际上也就是说0.75f是效率相对比较高的</li></ol> <h3 id="先说hashmap底层数组长度扩容为什么是2的幂次方数-其实就是为了使hash均匀分组"><a href="#先说hashmap底层数组长度扩容为什么是2的幂次方数-其实就是为了使hash均匀分组" class="header-anchor">#</a> 先说HashMap底层数组长度扩容为什么是2的幂次方数(其实就是为了使hash均匀分组)</h3> <ol><li>它其实涉及到了底层二进制算法，但目的很简单：就是为了使hash均匀分组</li> <li>当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了</li></ol> <h3 id="再来说hashmap的resize"><a href="#再来说hashmap的resize" class="header-anchor">#</a> 再来说HashMap的resize()</h3> <ol><li><p>当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize()。</p></li> <li><p>那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过扩容是2的幂次方数，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 &lt; 1000, 也就是说为了让0.75 * size &gt; 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&amp;的问题，也避免了resize的问题。</p> <blockquote><p>具体resize()的实现可以看：<a href="https://blog.csdn.net/u010890358/article/details/80496144" target="_blank" rel="noopener noreferrer">https://blog.csdn.net/u010890358/article/details/80496144<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p></blockquote></li></ol> <h2 id="hashmap面试题"><a href="#hashmap面试题" class="header-anchor">#</a> HashMap面试题</h2> <ol><li><p>hashmap的主要参数都有哪些？</p></li> <li><p>hashmap的数据结构是什么样子的？自己如何实现一个hashmap？</p></li> <li><p>hash计算规则是什么？</p></li> <li><p>说说hashmap的存取过程？</p></li> <li><p>说说hashmap如何处理碰撞的，或者说说它的扩容？</p> <p>==	<a href="https://www.cnblogs.com/qfxydtk/p/8734784.html" target="_blank" rel="noopener noreferrer">答案<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>	==</p></li> <li><p>针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？</p></li> <li><p>如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？</p></li> <li><p>为什么String, Interger这样的类适合作为键？</p></li> <li><p>HashMap与HashTable区别，能否让HashMap同步？</p> <p>==	<a href="https://blog.csdn.net/u012512634/article/details/72735183" target="_blank" rel="noopener noreferrer">答案<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>	==</p></li> <li><p>HashMap 的 table 的容量如何确定？loadFactor 是什么？ 该容量如何变化？这种变化会带来什么问题？</p></li> <li><p>HashMap 的遍历方式及其性能对比</p></li> <li><p>HashMap，LinkedHashMap，TreeMap 有什么区别？</p></li> <li><p>HashMap &amp; TreeMap &amp; LinkedHashMap 使用场景？</p></li> <li><p>为什么 ConcurrentHashMap 比 HashTable 效率要高，及ConcurrentHashMap？</p> <p>==	<a href="https://www.jianshu.com/p/75adf47958a7" target="_blank" rel="noopener noreferrer">答案<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>	==</p></li> <li><p><a href="https://blog.csdn.net/the_one_and_only/article/details/81665098" target="_blank" rel="noopener noreferrer">hashMap put()<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p></li></ol></div> <footer class="page-edit" style="display:none;"><div class="edit-link"><a href="https://github.com/f1ybird/edit/master/docs/views/java/HashMap.md" target="_blank" rel="noopener noreferrer">在 GitHub 上编辑此页！</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <div class="last-updated"><span class="prefix">Last Updated: </span> <span class="time">2020-06-21 23:07:31</span></div></footer> <!----> <!----></main> <!----> <div class="comments-wrapper" style="display:none;" data-v-0b87bb44><div class="valine-wrapper"><div id="valine"></div></div></div></div></div></div></div></div><div class="global-ui"><div class="back-to-ceiling" style="right:1rem;bottom:6rem;width:2.5rem;height:2.5rem;border-radius:.25rem;line-height:2.5rem;display:none;" data-v-44bd5a18 data-v-44bd5a18><svg t="1574745035067" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="5404" class="icon" data-v-44bd5a18><path d="M526.60727968 10.90185116a27.675 27.675 0 0 0-29.21455937 0c-131.36607665 82.28402758-218.69155461 228.01873535-218.69155402 394.07834331a462.20625001 462.20625001 0 0 0 5.36959153 69.94390903c1.00431239 6.55289093-0.34802892 13.13561351-3.76865779 18.80351572-32.63518765 54.11355614-51.75690182 118.55860487-51.7569018 187.94566865a371.06718723 371.06718723 0 0 0 11.50484808 91.98906777c6.53300375 25.50556257 41.68394495 28.14064038 52.69160883 4.22606766 17.37162448-37.73630017 42.14135425-72.50938081 72.80769204-103.21549295 2.18761121 3.04276886 4.15646224 6.24463696 6.40373557 9.22774369a1871.4375 1871.4375 0 0 0 140.04691725 5.34970492 1866.36093723 1866.36093723 0 0 0 140.04691723-5.34970492c2.24727335-2.98310674 4.21612437-6.18497483 6.3937923-9.2178004 30.66633723 30.70611158 55.4360664 65.4791928 72.80769147 103.21549355 11.00766384 23.91457269 46.15860503 21.27949489 52.69160879-4.22606768a371.15156223 371.15156223 0 0 0 11.514792-91.99901164c0-69.36717486-19.13165746-133.82216804-51.75690182-187.92578088-3.42062944-5.66790279-4.76302748-12.26056868-3.76865837-18.80351632a462.20625001 462.20625001 0 0 0 5.36959269-69.943909c-0.00994388-166.08943902-87.32547796-311.81420293-218.6915546-394.09823051zM605.93803103 357.87693858a93.93749974 93.93749974 0 1 1-187.89594924 6.1e-7 93.93749974 93.93749974 0 0 1 187.89594924-6.1e-7z" p-id="5405" data-v-44bd5a18></path><path d="M429.50777625 765.63860547C429.50777625 803.39355007 466.44236686 1000.39046097 512.00932183 1000.39046097c45.56695499 0 82.4922232-197.00623328 82.5015456-234.7518555 0-37.75494459-36.9345906-68.35043303-82.4922232-68.34111062-45.57627738-0.00932239-82.52019037 30.59548842-82.51086798 68.34111062z" p-id="5406" data-v-44bd5a18></path></svg></div><!----><div data-v-48108b4c><div class="DetailsOpenFlag" style="right:1rem;bottom:9rem;width:2.5rem;height:2.5rem;border-radius:.25rem;line-height:2.5rem;font-size:14px;font-weight:500;display:none;" data-v-48108b4c>
 展开 

</div></div></div></div>
    <script src="/assets/js/app.55c4f7c3.js" defer></script><script src="/assets/js/5.86109dd2.js" defer></script><script src="/assets/js/1.74974061.js" defer></script><script src="/assets/js/2.ab8aa845.js" defer></script><script src="/assets/js/63.84bfbbbf.js" defer></script><script src="/assets/js/18.cfe435f1.js" defer></script>
  </body>
</html>
